//在考场里，一排有 N 个座位，分别编号为 0, 1, 2, ..., N-1 。 
//
// 当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，
//那么学生就坐在 0 号座位上。) 
//
// 返回 ExamRoom(int N) 类，它有两个公开的函数：其中，函数 ExamRoom.seat() 会返回一个 int （整型数据），代表学生坐的位
//置；函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave(p) 时都保证有学生坐在
//座位 p 上。 
//
// 
//
// 示例： 
//
// 输入：["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[]
//,[4],[]]
//输出：[null,0,9,4,2,null,5]
//解释：
//ExamRoom(10) -> null
//seat() -> 0，没有人在考场里，那么学生坐在 0 号座位上。
//seat() -> 9，学生最后坐在 9 号座位上。
//seat() -> 4，学生最后坐在 4 号座位上。
//seat() -> 2，学生最后坐在 2 号座位上。
//leave(4) -> null
//seat() -> 5，学生最后坐在 5 号座位上。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= N <= 10^9 
// 在所有的测试样例中 ExamRoom.seat() 和 ExamRoom.leave() 最多被调用 10^4 次。 
// 保证在调用 ExamRoom.leave(p) 时有学生正坐在座位 p 上。 
// 
// Related Topics设计 | 有序集合 
//
// 👍 131, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

class ExamRoom1 {
    //leetcode submit region begin(Prohibit modification and deletion)
    // https://labuladong.gitee.io/algo/4/33/132/
    class ExamRoom {

        // 将端点 p 映射到以 p 为左端点的线段
        Map<Integer, int[]> startMap;
        // 将端点 p 映射到以 p 为右端点的线段
        Map<Integer, int[]> endMap;
        // 根据线段长度从小到大存放所有线段
        TreeSet<int[]> pq;
        int N;

        public ExamRoom(int n) {
            this.N = n;
            startMap = new HashMap<>();
            endMap = new HashMap<>();
            pq = new TreeSet<int[]>((a, b) -> {
                // 求出距离
                int a_distance = distance(a);
                int b_distance = distance(b);

                // 线段长度相同，左索引小的放在后边
                if (a_distance == b_distance) {
                    return b[0] - a[0];
                }

                // 按照线段升序
                return a_distance - b_distance;
            });

            // 加入虚拟线段，方便添加处理
            addInterval(new int[]{-1, N});
        }

        public int seat() {
            // 取出最长的线段
            int[] longest = pq.last();
            int x = longest[0];
            int y = longest[1];
            int seat = 0;

            if (x == -1) {
                seat = 0;
            } else if (y == N) {
                seat = N - 1;
            } else {
                seat = x + (y - x) / 2;
            }

            // 构造左右线段
            int[] left = new int[]{x, seat};
            int[] right = new int[]{seat, y};

            // 删除最大线段
            removeInterval(longest);

            // 添加2个线段
            addInterval(left);
            addInterval(right);

            return seat;
        }

        public void leave(int p) {
            int[] left = endMap.get(p);
            int[] right = startMap.get(p);

            int[] new_intv = {left[0], right[1]};

            // 删除旧的两个线段，必须先删除，否则先添加会覆盖两个map的值
            removeInterval(left);
            removeInterval(right);

            // 添加新线段
            addInterval(new_intv);
        }

        // 去除一个线段
        private void removeInterval(int[] intv) {
            pq.remove(intv);
            startMap.remove(intv[0]);
            endMap.remove(intv[1]);
        }

        // 增加一个线段
        private void addInterval(int[] intv) {
            pq.add(intv);
            startMap.put(intv[0], intv);
            endMap.put(intv[1], intv);
        }

        // 求距离的函数
        private int distance(int[] intv) {
            int left = intv[0];
            int right = intv[1];
            if (left == -1) return right;
            if (right == N) return N - left - 1;
            return (right - left) / 2;
        }
    }

/**
 * Your ExamRoom object will be instantiated and called as such:
 * ExamRoom obj = new ExamRoom(n);
 * int param_1 = obj.seat();
 * obj.leave(p);
 */
//leetcode submit region end(Prohibit modification and deletion)

}
